﻿using System;
using System.Collections;

namespace _136._只出现一次的数字
{
    /// <summary>
    /// https://leetcode.cn/problems/single-number/
    /// </summary>
    public class Solution
    {
        public int SingleNumber(int[] nums)
        {
            Hashtable ts = new Hashtable();
            for (int i = 0; i < nums.Length; i++)
            {
                if (ts.Contains(nums[i]))
                {
                    ts.Remove(nums[i]);
                    ts.Add(nums[i], 2);
                }
                else
                {
                    ts.Add(nums[i], 1);
                }
            }

            foreach (DictionaryEntry item in ts)
            {
                if (item.Value.ToString() == "1")
                {
                    return int.Parse(item.Key.ToString());
                }
            }
            return 0;
        }

        /// <summary>
        /// 异或算法： 
        /// 1.交换律：a ^ b ^ c = a ^ c ^ b
        /// 2.任何数于0异或为任何数 0 ^ n = n
        /// 3.相同的数异或为0: n ^ n = 0
        /// var a = [2,3,2,4,4]
        /// 2 ^ 3 ^ 2 ^ 4 ^ 4等价于 2 ^ 2 ^ 4 ^ 4 ^ 3 => 0 ^ 0 ^3 => 3
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public int SingleNumber2(int[] nums)
        {
            int r = 0;
            foreach (var item in nums)
            {
                r = r ^ item;
            }
            return r;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {

            Console.WriteLine(new Solution().SingleNumber(new int[] { 1, 1, 2 }));
            Console.WriteLine(new Solution().SingleNumber(new int[] { 4, 1, 2, 1, 2 }));

            Console.WriteLine(new Solution().SingleNumber2(new int[] { 1, 1, 2 }));
            Console.WriteLine(new Solution().SingleNumber2(new int[] { 4, 1, 2, 1, 2 }));
        }
    }
}
